package data_structure;

public class leetcode_0105 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    public TreeNode build(int[] preorder,int preleft,int preright, int[] inorder,int inleft,int inright){
        if(inright-inleft<0) return null;
        if(inright-inleft==0) return new TreeNode(inorder[inleft]);
        int numroot=preorder[preleft];
        TreeNode root=new TreeNode(numroot);
        int rootindex=0;
        for(int i=inleft;i<inright+1;++i){
            if(inorder[i]==numroot){
                rootindex=i;
                break;
            }
        }
        root.left=build(preorder,preleft+1,preleft+rootindex-inleft,inorder,inleft,rootindex-1);
        root.right=build(preorder,preleft+1+rootindex-inleft,preright,inorder,rootindex+1,inright);
        return root;

    }
}
